package easy.id_501_600;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Lee599 {
    public static void main(String[] args) {


    }
    public String[] findRestaurant(String[] list1, String[] list2) {
        Map<String,Integer> mp1=new HashMap<>();
        Map<String,Integer> mp2=new HashMap<>();

        for(int i=0;i<list1.length;i++){
            mp1.put(list1[i],i);
        }
        for(int i=0;i< list2.length;i++){
            mp2.put(list2[i],i );
        }
        List<String> commonKeys=new ArrayList<>();
        for(String key : mp1.keySet()){
            if(mp2.containsKey(key)){
                commonKeys.add(key);
            }
        }
        commonKeys.sort((str1, str2) -> {
            int sum1=mp1.get(str1)+mp2.get(str1);
            int sum2=mp1.get(str2)+mp2.get(str2);
            return Integer.compare(sum1, sum2);
        });
        List<String> result=new ArrayList<>();
        result.add(commonKeys.get(0));
        for(int i=1;i<commonKeys.size();i++){

            if(mp1.get(commonKeys.get(i))+mp2.get(commonKeys.get(i)) != mp1.get(commonKeys.get(0))+mp2.get(commonKeys.get(0))){
                break;
            }
            result.add(commonKeys.get(i));
        }
        String[] stringArray = result.toArray(new String[0]);
        return stringArray;
    }
}
